//八皇后递归解法
#include<stdio.h>
#define size 8
int Queen[size + 1] = {-1, -1, -1, -1, -1, -1, -1, -1, -1 };
int Count = 0;
int Check (int pointi, int pointj) {//判断某个皇后是否与已有皇后冲突
  int i;
  for (i = 0; i < pointi ; i++) {
    if (pointj == Queen[i] )
      return 0;//同一列拒绝
    if ((pointi - i ) == (pointj - Queen[i] ) ) 
      return 0;//同一主对角线拒绝
    if((pointi - i ) + (pointj - Queen[i] ) == 0)
      return 0;//同一副对角线拒绝
  }
  return 1;
}
void printQueen () {
  int i;
  printf("{ ");
  for ( i = 0; i < size ; i++) {
    printf("%d", Queen[i] + 1 );
    if ( i!= size - 1 ) {
      printf(" , ");
    }
  }
  printf(" }\n");
}

void recursionQueen (int QueenNumber) {
/*
 *递归方法
*/
  int i, j;
  for (i = 0; i < size; i++ ) {//从1~8遍历这一行的八个空位
    if (Check(QueenNumber, i ) ) {
      //如果可以放这个位置就记录下第QueenNumber个皇后的位置
      Queen[QueenNumber] = i;
      if (QueenNumber == (size - 1 ) ) {//如果八个皇后都放满了统计一下
        Count++;
        //输出每种情况
        printQueen();
        return;
      }
      int nextNumber = QueenNumber + 1;//还有皇后没放递归放下一个皇后
      recursionQueen(nextNumber);
    }
  }
  Queen[--QueenNumber] = -1;//如果这一行没有可放的位置说明上一行皇后放的位置不行，要为上一个皇后寻找新的可放位置
  return;
}
void unrecursionQueen (int line) {
/*
 *非递归方法
*/
  int i, j;
	//在数组中为0-7列
	for (int i = 0; i < 8; i++) {
		//对于固定的行列，检查是否和之前的皇后位置冲突
		if (Check(line, i)) {
			//不冲突，以行为下标的数组位置记录列数
			Queen[line] = i;
			//如果最后一样也不冲突，证明为一个正确的摆法
			if (line == 7 ) {
				//统计摆法的Counts加1
				Count++;
				//输出这个摆法
        printQueen ();
				//每次成功，都要将数组重归为0
				Queen[line] = 0;
				return;
			}
			//继续判断下一样皇后的摆法，递归
			unrecursionQueen(line + 1);
			//不管成功失败，该位置都要重新归0，以便重复使用。
			Queen[line] = 0;
		}
	}
}
int main (void) {
  int n = 1;
  while (n != 0) {
    printf("\n--------八皇后问题--------\n请输入需要使用的方法:\n1.递归法\n2.非递归法\n0.退出\n");
    scanf("%d", &n);
    switch (n) {
      case 1:
        recursionQueen(0);
        printf("%d", Count);
        break;
      case 2:
        unrecursionQueen(0);
        printf("%d", Count);
        break;
      default:
        return 0;
        break;
    }
    Count = 0;
  }
  return 0;
}